#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int main(){
    return 0;
}

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        subInorderTraversal(root, res);
        return res;
    }

    void subInorderTraversal(TreeNode *root, vector<int> &vec){
        if(!root) 
            return;
        if(root->left)
            subInorderTraversal(root->left, vec);
        vec.push_back(root->val);
        if(root->right)
            subInorderTraversal(root->right, vec);
    }

    struct NodePack{
        TreeNode *pNode;
        int depth;
        NodePack(TreeNode* _pNode, int _depth):pNode(_pNode),depth(_depth){};
    };

    vector<vector<int> > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        vector<vector<int> > res;
        if(!root)
            return res;

        queue<NodePack> que;
        NodePack rootPack(root,0);
        que.push(rootPack);
        int curDepth = 0;
        while(!que.empty()){
            NodePack curPack = que.front();
            que.pop();
            while(curPack.depth >= res.size()){
                vector<int> tmp;
                res.push_back(tmp);
            }
            res[curPack.depth].push_back(curPack.pNode->val);
            // next
            if(curPack.pNode->left){
                NodePack tmpPack(curPack.pNode->left, curPack.depth+1);
                que.push(tmpPack);
            }
            if(curPack.pNode->right){
                NodePack tmpPack(curPack.pNode->right, curPack.depth+1);
                que.push(tmpPack);
            }
        }
        return res;
        
    }

    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

        vector<vector<int> > res;
        if(!root)
            return res;

        queue<NodePack> que;
        NodePack rootPack(root,0);
        que.push(rootPack);
        int curDepth = 0;
        while(!que.empty()){
            NodePack curPack = que.front();
            que.pop();
            while(curPack.depth >= res.size()){
                vector<int> tmp;
                res.push_back(tmp);
            }
            res[curPack.depth].push_back(curPack.pNode->val);
            // next
            if(curPack.pNode->left){
                NodePack tmpPack(curPack.pNode->left, curPack.depth+1);
                que.push(tmpPack);
            }
            if(curPack.pNode->right){
                NodePack tmpPack(curPack.pNode->right, curPack.depth+1);
                que.push(tmpPack);
            }
        }
        for(int i=1; i<res.size(); i+=2){
            vector<int> tmp(res[i].crbegin(), res[i].crend());
            res[i] = tmp;
        }
        return res;
    }


};